当前位置:  编程技术>综合

[1]数据结构 uva 101 - The Blocks Problem

 

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=37

 

题目意思：

    开始给定编号为0-n的数分别在1-n栈里，然后执行四种操作，求最后这n个栈中的数据情况

    四种操作规则：

    1.move a onto b

把a所在栈a上面的数据回归到初始状态，把b所在栈b上面的数据回归到初始状态，然后把a放到b上面

    2.move a over b

把a所在栈a上面的数据回归到初始状态，然后把a放到b上面

    3.pile a onto b

把b所在栈b上面的数据回归到初始状态,然后把a所在栈包括a元素在内的所有元素按在该栈的顺序不变，全部移到b所在的栈上

   4.pile a over b

把a所在栈包括a元素在内的所有元素按在该栈的顺序不变，全部移到b所在的栈上

 

解题思路：

   用栈来模拟执行过程，注意数据为0-n-1，回归的时候注意加一。细节详见代码

 

代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define eps 1e-6
#define INF (1<<20)
#define PI acos(-1.0)
using namespace std;


struct Stack  //模拟栈
{
    int top;
    int save[100];

    int pop()
    {
        return save[top--];
    }

    int push(int n)
    {
        ++top;

        return save[top]=n;
    }

    bool empty()
    {
        if(top==0)
            return true;
        return false;
    }

    void clear()
    {
        top=0;
    }

    int finda(int a)
    {
        for(int i=1;i<=top;i++)  //在栈中找数的位置
            if(save[i]==a)
                return i;
        return 0;
    }

};

Stack stack[100];

int n;

int find(int a)  //找数a属于哪一个栈
{
    for(int i=1;i<=n;i++)
    {

        int j=stack[i].finda(a);

        if(j)
           return i;
    }

}

void removeup(int local,int a) //将a上面的元素全部回归
{
    //while(stack[local].save[stack[local].top]!=a)


    int limit=stack[local].finda(a);

    for(int i=limit+1;i<=stack[local].top;i++)
    {
        int temp=stack[local].save[i];

        stack[temp+1].push(temp);
       /* stack[temp+1].clear();      //注意回归时应与加一对应，坑死了
        stack[temp+1].push(temp);*/
    }

    stack[local].top=limit;  //注意现在该栈的元素个数

    return ;
}

void removewhole(int locala,int a,int localb) //将a所在栈包括a以及以上的所有元素全部按顺序移到b所在栈上
{

    int i=stack[locala].finda(a);  //先找到a的位置
    int temp=i;

    for(;i<=stack[locala].top;i++)
    {
        stack[localb].push(stack[locala].save[i]);

    }
    stack[locala].top=temp-1; //注意更新栈a的元素个数



    return ;
}


void moveonto(int a,int b)
{
    int tempa=find(a),tempb=find(b);

    if(tempa==tempb)
        return ;

    removeup(tempa,a);
    removeup(tempb,b);

    stack[tempb].push(a);  //将a移向b
    stack[tempa].top--;
    return ;
}

void moveover(int a,int b)
{
    int tempa=find(a),tempb=find(b);

    if(tempa==tempb)
        return ;

    removeup(tempa,a);
    stack[tempb].push(a);  //将a移向b
    stack[tempa].top--;
    return ;
}

void pileonto(int a,int b)
{
    int tempa=find(a),tempb=find(b);

    if(tempa==tempb)
        return ;

    removeup(tempb,b);
    removewhole(tempa,a,tempb);
    return ;
}

void pileover(int a,int b)
{
    int tempa=find(a),tempb=find(b);

    if(tempa==tempb)
        return ;

    removewhole(tempa,a,tempb);
}

void print()
{
    for(int i=1;i<=n;i++)
        {
            printf("%d:",i-1);
            if(!stack[i].empty())
            {
                for(int j=1;j<=stack[i].top;j++)
                    printf(" %d",stack[i].save[j]);

            }
            putchar('\n');
        }
    return ;
}

int main()
{
    int a,b;
    char com1[20],com2[20];

    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
        {
            stack[i].clear();
            stack[i].push(i-1);
        }
        //print();

        while(cin>>com1&&strcmp(com1,"quit"))
        {
            scanf("%d%s%d",&a,com2,&b);
            if(a==b)
                continue;

            if(strcmp(com1,"move")==0)
            {
                if(strcmp(com2,"onto")==0)
                    moveonto(a,b);
                else
                    moveover(a,b);
            }
            else
            {
                if(strcmp(com2,"onto")==0)
                    pileonto(a,b);
                else
                    pileover(a,b);
            }
           // print();

        }
        print();


    }

    return 0;
}

 

 

 

 

[2]扩展ImageView使可旋转

继承ImageView,增加angle属性，重写OnMeasure和OnDraw方法

package com.upon.common.view;

import android.content.Context;
import android.content.res.TypedArray;
import android.graphics.Canvas;
import android.util.AttributeSet;
import android.widget.ImageView;

import com.upon.xxxx.R;

public class UponRotateImageView extends ImageView {

	private int mAngle;

	public UponRotateImageView(Context context, AttributeSet attrs, int defStyle) {
		super(context, attrs, defStyle);
		loadAttributes(context, attrs);
	}

	public UponRotateImageView(Context context, AttributeSet attrs) {
		super(context, attrs);
		loadAttributes(context, attrs);
	}

	public UponRotateImageView(Context context) {
		super(context);
	}

	private void loadAttributes(Context context, AttributeSet attrs) {
		TypedArray arr = context.obtainStyledAttributes(attrs, R.styleable.RotateImageView);
		mAngle = arr.getInteger(R.styleable.RotateImageView_angle, 0);
		arr.recycle();
	}

	public int getAngle() {
		return mAngle;
	}

	public void setAngle(int angle) {
		mAngle = angle;
	}

	@Override
	protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
		int w = getDrawable().getIntrinsicWidth();
		int h = getDrawable().getIntrinsicHeight();
		double a = Math.toRadians(mAngle);

		int width = (int) (Math.abs(w * Math.cos(a)) + Math.abs(h * Math.sin(a)));
		int height = (int) (Math.abs(w * Math.sin(a)) + Math.abs(h * Math.cos(a)));

		setMeasuredDimension(width, height);
		super.onMeasure(widthMeasureSpec, heightMeasureSpec);
	}

	@Override
	protected void onDraw(Canvas canvas) {
		canvas.save();
		canvas.rotate(mAngle % 360, getWidth() / 2, getHeight() / 2);
		getDrawable().draw(canvas);
		canvas.restore();
	}
}

attrs.xm文件中增加angle属性

<?xml version="1.0" encoding="utf-8"?>
<resources>
    <declare-styleable name="RotateImageView">
        <attr name="angle" format="integer" />
    </declare-styleable>

</resources>

使用UponRotateImageView

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:upon="http://schemas.android.com/apk/res/com.upon.xxxx"
    android:layout_width="wrap_content"
    android:layout_height="wrap_content" >

    <com.upon.common.view.UponRotateImageView
        android:id="@+id/bkg_img"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:src="/blog_article/@drawable/conquer_nation_bkg/index.html"
        upon:angle="45" />

</RelativeLayout>

已有 0 人发表留言，猛击->>这里<<-参与讨论


ITeye推荐

• —软件人才免语言低担保 赴美带薪读研！—

[3]linuxthreads管理线程原理详解

linuxthreads管理线程原理详解

为什么A程序创建了10个线程, 但是ps时却会出现11个A进程了. 因为linuxthreads自动创建了一个管理线程. 
当程序开始运行时, 并没有管理线程存在(因为尽管程序已经链接了pthread库, 但是未必会使用多线程). 
程序第一次调用pthread_create时, linuxthreads发现管理线程不存在, 于是创建这个管理线程. 这个管理线程是进程中的第一个线程(主线程)的儿子.
然后在pthread_create中, 会通过pipe向管理线程发送一个命令, 告诉它创建线程. 即是说, 除主线程外, 所有的线程都是由管理线程来创建的, 管理线程是它们的父亲.

【一个线程退出】
于是, 当任何一个子线程退出时, 管理线程将收到SIGUSER1信号(这是在通过clone创建子线程时指定的). 管理线程在对应的sig_handler中会判断子线程是否正常退出, 如果不是, 则杀死所有线程, 然后自杀.
那么, 主线程怎么办呢? 主线程是管理线程的父亲, 其退出时并不会给管理线程发信号. 于是, 在管理线程的主循环中通过getppid检查父进程的ID号, 如果ID号是1, 说明父亲已经退出, 并把自己托管给了init进程(1号进程). 这时候, 管理线程也会杀掉所有子线程, 然后自杀.

可见, 线程的创建与销毁都是通过管理线程来完成的, 于是管理线程就成了linuxthreads的一个性能瓶颈. 
创建与销毁需要一次进程间通信, 一次上下文切换之后才能被管理线程执行, 并且多个请求会被管理线程串行地执行.

【总结】
当一个线程退出时：
1.正常退出========  其他线程继续运行。
2.非正常退出======  进程结束。

当进程退出时：
进程和所有线程一起退出。
=======================================================
父子进程中若父进程退出，而不等待子进程，子进程会变为僵尸进程。